package compute.the.intersection.of.two.array;

import java.util.Arrays;

/**
 * @Time 2019/12/23
 * @author 王光浩
 * @Need 给出两个整型数组，找出两个数组中所有重复的元素（结果不去重）。比如num1数组为[1,2,2,3]，num2数组
 *       为[2,2],则最后结果为[2,2]。
 * @Method 先将两个数组进行排序，然后使用双指针来完成对重复元素的查找。
 *         思路：将两个数组从小到大排完序后，使用两个指针分别指向两个对应的数组，然后比较两个指针指向下标的对应
 *               元素的值，如果相等则将该元素值保存起来，然后两个指针都后移一位；如果前一个指针指向的元素比后一个
 *               指向的元素值大责后一个指针后移一位；否则将前一个指针后移一位，如果两个指针中有一个率先超过了其所
 *               对应数组的最大下标，则循环结束。然后将结果返回即可。
 *         复杂度分析：时间复杂度O（nlogn），空间复杂度O（1）
 */
public class OtherMethod {
    public int[] intersect(int[] nums1, int[] nums2) {
    	//先将两个数组进行排序
    	Arrays.sort(nums1);
    	Arrays.sort(nums2);
    	//使用双指针获取两个数组中的重复元素
    	int indexOf1=0;                 //第一个指针，保存nums1中下一个位置待比较元素的下标。
    	int indexOf2=0;                 //第二个指针，保存nums2中下一个位置待比较元素的下标。
    	int total=0;                    //用于指向结果数组中下一个符合要求元素的保存下标
    	int nums1Len=nums1.length;
    	int nums2Len=nums2.length;
    	//使用循环查找两个数组中重复的元素
    	while(indexOf1<nums1Len && indexOf2<nums2Len) {
    		if(nums1[indexOf1]>nums2[indexOf2]) 
    			indexOf2++;
    		else if(nums1[indexOf1]<nums2[indexOf2])
    			indexOf1++;
    		else {
    			nums1[total++]=nums1[indexOf1]; //将结果保存在nums1数组中，这样有利于节约空间
    			indexOf1++;
    			indexOf2++;
    		}
    	}
    	return Arrays.copyOf(nums1, total);
    }
}
